import util.TreeNode;

/**
 * Created by loso on 2017/3/10.
 */
public class _235_LowestCommonAncestorOfABinarySearchTree {


    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
        if (root == null)
            return null;
        int min = p.val < q.val? p.val:q.val;
        int max = p.val > q.val? p.val:q.val;

        if(findNode(root.left,max)){
            return lowestCommonAncestor(root.left,p,q);
        }
        if (findNode(root.right,min)){
            return lowestCommonAncestor(root.right,p,q);
        }
        return root;
    }

    public boolean findNode (TreeNode root , int target){
        if (root == null){
            return false;
        }
        if (root.val == target){
            return true;
        }
        if (root.val > target){
            return findNode(root.left,target);
        }
            return findNode(root.right,target);
    }
}
